//节点类型
template<class T>
struct ListNode
{
	ListNode<T>* _pPre;
	ListNode<T>* _pNext;
	T _val;
};

//迭代器类型
template<class T, class Ref, class Ptr> //利用参数列表决定是否为const迭代器
class ListIterator
{
	typedef ListNode<T> Node; //节点指针
	typedef ListIterator<T, Ref, Ptr> Self; //迭代器，可以是const版本的，也可以是非const版本的，
public:                                     //由Ref Ptr决定
	Ref operator*()
	{}

	Ptr operator->()
	{}

	Self& operator++()
	{}

	Node* _node;
};

//链表类型
template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T&> const_iterator;//利用参数列表决定是否为const迭代器
private:
	Node* _pHead;
};

//--------------------------------------------------------------//

//颜色
enum Colour
{
	RED,
	BLACK
};

//节点
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data; //有效信息
	Colour _col; //颜色
};

//迭代器
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
public:
	Ref operator*()
	{}

	Ptr operator->()
	{}

	Self& operator++()
	{}
	
	Node* _node;
};

//红黑树
template<class K, class T, class KeyOfT>
struct RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef RBTreeIterator<T, T&, T*> iterator;
	typedef RBTreeIterator<T, const T&, const T*> const_iterator;

	//KeyOfT kot; 仿函数，用来取出T里的值用以比较

private:
	Node* _root;
};

//set封装
template < class K>
class set
{
public:

	//仿函数，用来取到用以比较的值
	struct SetKeyOfT
	{
		const K& operator()(const K& k)
		{
			return k;
		}
	};
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator; //set不允许修改
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
	iterator begin()
	{}

private:
	RBTree<K, K, SetKeyOfT> _t;
};


template < class K, class V>
class map
{
public:
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};

	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //返回的是pair的second的引用
	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;

	iterator begin()
	{}

private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
